package 双指针.盛雨水;
/**
 * 题目描述：
 * 到时看力扣图理解
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 力扣地址：https://leetcode-cn.com/problems/trapping-rain-water/
 * 力扣第：42
 * 就是下雨了，水在凹下去的地方，你要算：一共能存多少格水
 * */
/**
 * 核心思路：
 * 每一根柱子上方能装多少水，只取决于它左边最高柱子，右边最该柱子，和他自己的高度
 * 左右比较最低高度减去它自己的高度就是水的容量
 * */
/**
 * 暴力思路：
 * 向左扫一遍，找最大高度 leftMax
 * 向右扫一遍，找最大高度 rightMax
 * 算这一格能装多少水
 * 时间复杂度：O(n²)（每个位置都要往左右扫）
 * */
/**
 * 题目思路：
 * 左指针left从左往右走
 * 右指针right从右往左走
 * 同时维护：
 * leftMax:到目前为止左边出现的最高柱子高度
 * rightMax:到目前为止右边出现最高柱子高度
 * 每次移动[较矮的一边],并在移动时，把这一边能接的水加进去
 * 如果当前高度比两边高度较矮的高度高，说明蓄水不了了，将这个高度赋给两边叫矮的高度
 * */
class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0; // 结果：总的蓄水量

        while(left < right){
            if(height[left] < height[right]){
                // 左边矮，决定的是左边这格的蓄水量
                if(height[left] >= leftMax){
                    leftMax = height[left]; // 更新左边最高
                }else{
                    // 左边这个能接的水 = leftMax - height[left]
                    res += leftMax - height[left];
                }
                left++;
            }else{
                // 右边矮，决定的是右边这格的水量
                if(height[right] >= rightMax){
                    rightMax = height[right]; // 更新右边最高
                }else{
                    // 右边这格能接的水 = rightMax - height[right]
                    res += rightMax - height[right];
                }
                right--;
            }
        }
        return res;
    }
}